#include "lru.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 函数：模拟LRU页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */

struct node {
  int vpn;
  int priority;
  struct node* next;
};

static int p = 0;

struct node* create(int num) {
  struct node* head = malloc(sizeof(struct node));
  head -> next  = NULL;
  head -> vpn = -1;
  head -> priority = p;
  for(int i = 0; i < num - 1; i++) {
    struct node* temp = malloc(sizeof(struct node));
    temp -> vpn = -1;
    temp -> priority = p;
    temp -> next = head -> next;
    head -> next = temp;
  }
  return head;
}

void del(struct node* head) {
  struct node *cur = head;
  while(cur != NULL) {
    struct node* temp = cur;
    cur = cur -> next;
    free(temp);
  }
}

struct node* exist(int vpn, struct node* head) {
  struct node *cur = head;
  while(cur != NULL) {
    if(cur -> vpn == vpn) return cur;
    cur = cur -> next;
  }
  return NULL;
}

void insert(struct node* head, int vpn) {
  struct node* n = exist(vpn, head);
  if(!n) {
    int min = 65535;
    struct node* p_min = NULL;
    for(n = head; n != NULL; n = n -> next) {
      if(n -> priority < min) {
        p_min = n;
        min = n -> priority;
      }
    }
    n = p_min;
  }
  n -> priority = ++p;
  n -> vpn = vpn;
}

void print(struct node* head, int vpn) {
  struct node *cur = head;
  printf("Access:%d,Frames: [", vpn);
  while(cur != NULL) {
    printf("%d", cur -> vpn);
    if(cur -> next) printf(",");
    cur = cur -> next;
  }
  printf("]\n");
}

void
lru_page_replacement (char *queue_frames, int num) {
  // TODO
  struct node* head = create(num);
  char * token = strtok(queue_frames, ",");
  while(token != NULL) {
    int vpn = atoi(token);
    insert(head, vpn);
    print(head, vpn);
    token = strtok(NULL, ",");
  }
}
